package logic.strategy;

import java.util.ArrayList;
import java.util.Collections;

public class WeightedGraph {

	private int [][]  edges;  // adjacency matrix
	private Object [] labels;
	
	private int [][]  preds;
	private int [][]  dists;
	private boolean [] calculated;

	public WeightedGraph (int n) {
		edges  = new int [n][n];
		labels = new Object[n];
		preds = new int [n][n];
		dists = new int [n][n];
		calculated = new boolean [n];
	}

	public int size() { return labels.length; }

	public void   setLabel (int vertex, Object label) { labels[vertex]=label; }
	public Object getLabel (int vertex)               { return labels[vertex]; }

	public void    addEdge    (int source, int target, int w)  { edges[source][target] = w; }
	public boolean isEdge     (int source, int target)  { return edges[source][target]>0; }
	public void    removeEdge (int source, int target)  { edges[source][target] = 0; }
	public int     getWeight  (int source, int target)  { return edges[source][target]; }

	public int [] neighbors (int vertex) {
		int count = 0;
		for (int i=0; i<edges[vertex].length; i++) {
			if (edges[vertex][i]>0) count++;
		}
		final int[]answer= new int[count];
		count = 0;
		for (int i=0; i<edges[vertex].length; i++) {
			if (edges[vertex][i]>0) answer[count++]=i;
		}
		return answer;
	}

	public void print () {
		for (int j=0; j<edges.length; j++) {
			System.out.print (labels[j]+": ");
			for (int i=0; i<edges[j].length; i++) {
				if (edges[j][i]>0) System.out.print (labels[i]+":"+edges[j][i]+" ");
			}
			System.out.println ();
		}
	}

	// Dijkstra's algorithm to find shortest path from s to all other nodes
	private void dijkstra (int s) {

		final int [] dist = new int [size()];  // shortest known distance from "s"
		final int [] pred = new int [size()];  // preceding node in path
		final boolean [] visited = new boolean [size()]; // all false initially

		for (int i=0; i<dist.length; i++) {
			dist[i] = Integer.MAX_VALUE;
			pred[i] = -1;
		}
		dist[s] = 0;

		for (int i=0; i<dist.length; i++) {
			// next is the closest vertex to s that wasn't visited yet
			// minHeap.removeMin()
			final int next = minVertex (dist, visited);
			if(next == -1)
			{
				preds[s] = pred;
				dists[s] = dist;
				calculated[s] = true; 
								
				return; // graph is not connected and all of the countries that are reachable to S were visitied
			}

			visited[next] = true; // mark visited

			// The shortest path to next is dist[next] and via pred[next].

			final int [] n = neighbors (next); // relax all neighboring to next
			for (int j=0; j<n.length; j++) {
				final int v = n[j];
				final int d = dist[next] + getWeight(next,v);
				if (dist[v] > d) { // if you can get closer to s via next, rather than what you currently can, relax yourself.
					dist[v] = d;
					pred[v] = next;
				}
			}
		}
		
		preds[s] = pred;  // (ignore pred[s]==0!)
		dists[s] = dist;
		calculated[s] = true; 
	}

	private int minVertex (int [] dist, boolean [] v) {

		int x = Integer.MAX_VALUE;
		int y = -1;   // graph not connected, or no unvisited vertices
		for (int i=0; i<dist.length; i++) {
			if (!v[i] && dist[i]<x) {y=i; x=dist[i];}
		}
		return y;
	}
	
	public ArrayList<Object> getShortestPath(int source, int target) {
		
		ArrayList<Object> path = new ArrayList<Object>();
		
		if (!calculated[source])
			dijkstra(source);
		
		int vertex = target;		
		path.add(labels[vertex]);
		
		while (vertex != source && vertex != -1) {
			path.add(labels[preds[source][vertex]]);
			vertex = preds[source][vertex];
		}
		
		Collections.reverse(path);
		
		return path; 
		
	}
	
	public int getShortestPathWeight(int source, int target) {
		
		if (!calculated[source])
			dijkstra(source);
		
		return dists[source][target];
		
	}
	
	
	
	

}


